#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <algorithm>
using namespace std;
#ifndef NULL
#define NULL 0
#endif
  struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
  };

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function

		ListNode* last = NULL, *prev = NULL,*current = head;
		while(current)
		{
			if(current->val<x)
			{
				if(last)
				{
					if(last==prev)
					{
						last=prev=current;
						current= current->next;
					}
					else
					{
						prev->next = current->next;
						current->next = last->next;
						last->next = current;
						last = current;
						current = current->next;
					}
				}
				else
				{
					if(prev)
					{
						prev->next = current->next;
						current->next = head->next;
						head->next = current;
						swap(head->val,current->val);
						last = head;
						current = prev->next;
					}
					else
					{
						prev = last = current;
						current = current->next;
					}
				}
			}
			else
			{
				prev = current;
				current = current->next;
			}
		}

		return head;        
    }
};
#endif
